package DataModel.SegmentTree;

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.LinkedList;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;

import DataModel.LayoutManager.CEdge;

/**
 * @author Guy Bootman
 * Implementation of segment tree, used as status for sweeping line.
 *
 */
public class SegmentTreeImpl implements SegmentTree{

	protected ArrayList<CEdge> edges = null;
	protected SegmentTreeNode root  = null;
	protected ArrayList<Long> sortedEndpoints = null;
	char axis = 'y';
	
	/**
	 * Constructore for Segment tree 
	 * @param edges all edges in the "world" the tree might contain
	 * @param axis - direction edges can be  parallel to x axis  or parallel to y axis
	 */
	public SegmentTreeImpl(ArrayList<CEdge> edges,char axis) {
		this.edges = edges;
		this.axis=axis;
		if (!buildEmptyTree(this.edges)) {
			System.err.println("Error in intializing empty segment tree");
		}
	}
	
	//Asuming edges are sorted
	//Creating sorted enpoints

	private ArrayList<Long> sortEndpoints(ArrayList<CEdge> edges) {
		HashMap<Long, Boolean> endpointsHash = new HashMap<Long, Boolean>();
		
		for (int i=0; i<edges.size(); i++) {
			CEdge edge = edges.get(i);
			long point1=getEdgeBegin(edge);
			long point2=getEdgeEnd(edge);
			
			endpointsHash.put(point1, true);
			endpointsHash.put(point2, true);
		
	
		}
		Set<Long> keys = endpointsHash.keySet();
		
		ArrayList<Long> endpointsList = new ArrayList<Long>(keys);
		Collections.sort(endpointsList);
		return endpointsList;
		
		
	}		
	//To Change To Private!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
	private boolean buildEmptyTree(ArrayList<CEdge> edges) {
		this.sortedEndpoints = sortEndpoints(edges);
		 
		if (this.sortedEndpoints.size() <= 1 ) {
			System.err.println("Error, bad number of endpoints " +this.sortedEndpoints.size() );
			
			return false;
		}
		Queue<SegmentTreeNode> q= new LinkedList<SegmentTreeNode>();
		long begin 	=this.sortedEndpoints.get(0);
		long end = this.sortedEndpoints.get(this.sortedEndpoints.size()-1);
		this.root  =  createTreeNode(begin, end);
		q.add(this.root);
		
		// System.out.println("("+this.root.getBegining()+"  "+this.root.getEnd()+")");
		
		while (!q.isEmpty()) {
			SegmentTreeNode parent  = q.poll();
			// System.out.println("("+parent.getBegining()+"  "+parent.getEnd());
			int beginIndex = this.sortedEndpoints.indexOf(parent.getBegining());
			int endIndex = this.sortedEndpoints.indexOf(parent.getEnd());
			int median = (beginIndex + endIndex)/2;
			if (endIndex == (beginIndex+1)) {
				continue;
			}
			SegmentTreeNode leftSon =  createTreeNode(parent.getBegining(), this.sortedEndpoints.get(median));
			parent.setLeftSon(leftSon);
			SegmentTreeNode rightSon =  createTreeNode(this.sortedEndpoints.get(median),parent.getEnd());
			parent.setRightSon(rightSon);
			q.add(leftSon);
			q.add(rightSon);
			
		}
		return true;
	}		

	public boolean insert(CEdge edge) {
		if (this.root == null) {
			System.err.println("Error, tree not initialized");
		}
		long b = getEdgeBegin(edge);
		long e = getEdgeEnd(edge);
		
//		 if the edge is downward or backward direction
		if (b>e) {
			b = getEdgeEnd(edge);
			e = getEdgeBegin(edge);
		}
		
		Stack<SegmentTreeNode> s = new Stack<SegmentTreeNode>();
		s.push(this.root);
		
		while (!s.isEmpty()) {
			SegmentTreeNode tNode = s.pop();
			
			if(b <= tNode.getBegining() && tNode.getEnd() <= e) {
				tNode.insertData(edge.getID());
				
				continue;
			}
			
			if (tNode.rightSon() != null ) {
				if (tNode.rightSon().getBegining() < e) {
					s.push(tNode.rightSon());
				}
			}
			if (tNode.leftSon()  != null ) {
				if (b < tNode.leftSon().getEnd()) {
					s.push(tNode.leftSon());
				}		
			}
		}
		return true;
	}

	public boolean remove(CEdge edge) {
		if (this.root == null) {
			System.err.println("Error, tree not initialized");
		}
		long b = getEdgeBegin(edge);
		long e = getEdgeEnd(edge);
		
		// if the edge is downward or backward direction
		if (b>e) {
			b = getEdgeEnd(edge);
			e = getEdgeBegin(edge);
		}
		
		Stack<SegmentTreeNode> s = new Stack<SegmentTreeNode>();
		s.push(this.root);
		
		while (!s.isEmpty()) {
			SegmentTreeNode tNode = s.pop();
			
			if(b <= tNode.getBegining() && tNode.getEnd() <= e) {
				tNode.removeData(edge.getID());
				continue;
			}
			
			if (tNode.rightSon() != null ) {
				if (tNode.rightSon().getBegining() < e) {
					s.push(tNode.rightSon());
				}
			}
			if (tNode.leftSon()  != null ) {
				if (b < tNode.leftSon().getEnd()) {
					s.push(tNode.leftSon());
				}		
			}
		}
	
		return true;
	}

	public SegmentTreeNode getRoot() {
		return root;
	}
	private int getEdgeBegin(CEdge edge) {
		if (this.axis == 'x') {
			return edge.getStartPoint().x;
			} else {
			return edge.getStartPoint().y;
			}
	}
	private int getEdgeEnd(CEdge edge) {
		if (this.axis == 'x') {
			return edge.getEndPoint().x;		
		} else {
			return edge.getEndPoint().y;
		}	
	}
	protected SegmentTreeNode createTreeNode(long begin, long end) {
		SegmentTreeNode newNode = new SegmentTreeNodeImpl(begin,end);
		return newNode; 
		
	}	
	public ArrayList<Long> stabbingQuery(long coord){
		Hashtable<Long,Boolean> res = new Hashtable<Long,Boolean>();
		

		Stack<SegmentTreeNode> s = new Stack<SegmentTreeNode>();
		s.push(this.root);
		
		while (!s.isEmpty()) {
			SegmentTreeNode tNode = s.pop();
			for (int i=0;i<tNode.getData().size();i++) {
				res.put((Long) tNode.getData().get(i),true);
			}
			
			if (tNode.rightSon() != null ) {
				if (tNode.rightSon().getBegining() <= coord) {
					s.push(tNode.rightSon());
				}
			}
			if (tNode.leftSon()  != null ) {
				if (coord <= tNode.leftSon().getEnd()) {
					s.push(tNode.leftSon());
				}		
			}
		}
	
		return new ArrayList<Long>(res.keySet());
		
	}

	public ArrayList<Long> rangeQuery(long begin, long end) {
		Hashtable<Long,Boolean> result =  new Hashtable<Long, Boolean>();
		int startPoint  = sortedEndpoints.indexOf(begin);
		int endPoint = sortedEndpoints.indexOf(end);
		for (int i = startPoint; i<=endPoint ; i++) {
			long qPoint = sortedEndpoints.get(i);
			ArrayList qEdges = stabbingQuery(qPoint);
			ListIterator it = qEdges.listIterator();
			while (it.hasNext()) {
				result.put((Long) it.next(), true);
			}
		}
		return new ArrayList<Long>(result.keySet());
	}
	public static void printSegmentTree(SegmentTree t) {
		SegmentTreeNode root = t.getRoot();

		Queue<SegmentTreeNode> q = new LinkedList<SegmentTreeNode>();

		q.add(root);

		int i=1;
		int level=0;
		while (!q.isEmpty()) {
			i--;
			SegmentTreeNode current = q.poll();
			System.out.print("  ("+current.getBegining()+" "+current.getEnd()+") ");
			System.out.print("edges: "+current.getData().toString()+".");
			if (i==0) {
				System.out.print("\n");
				level++;
				i =  (int) Math.pow(2,level);
			}
			if (current.leftSon() != null)  {
				q.add(current.leftSon());
			}
			if (current.rightSon() != null)  {
				q.add(current.rightSon());
			}
		}


	}
	    
}		
